package com.tongtech.proxy.objects;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindAllAnagrams {
    public static List<Integer> findAllAnagrams(String s, String p) {
        // 创建一个哈希表来存储 p 中每个字符的出现次数
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : p.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // 初始化窗口大小和起始索引
        int windowSize = p.length();
        int start = 0;

        // 存储所有字母异位词的起始索引
        List<Integer> result = new ArrayList<>();

        // 遍历源字符串
        for (int i = 0; i < s.length(); i++) {
            // 更新窗口中字符的出现次数
            char c = s.charAt(i);
            if (charCount.containsKey(c)) {
                charCount.put(c, charCount.get(c) - 1);
            }

            // 判断窗口是否满足条件
            boolean allZero = true;
            for (Integer count : charCount.values()) {
                if (count != 0) {
                    allZero = false;
                    break;
                }
            }

            if (allZero) {
                // 找到一个字母异位词
                result.add(start);
            }

            // 缩小窗口
            if (i >= windowSize - 1) {
                char c2 = s.charAt(start);
                if (charCount.containsKey(c2)) {
                    charCount.put(c2, charCount.get(c2) + 1);
                }
                start++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";

        List<Integer> result = findAllAnagrams(s, p);

        System.out.println(result);
    }
}
